package medium.差分数组;

/**
 * 创建时间：2025-05-21 15:56
 */
public class 零数组变换II_3356 {
    public int minZeroArray(int[] nums, int[][] queries) {
        int l = -1, r = queries.length + 1;
        while (l + 1 < r) {
            int mid = (l + r) >>> 1;
            if (check(mid, nums, queries)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r <= queries.length ? r : -1;
    }

    boolean check(int k, int[] nums, int[][] queries) {
        int n = nums.length;
        int[] diff = new int[n+1];
        for (int i = 0; i < k; i++) {
            int[] q = queries[i];
            int num = q[2], from = q[0], to = q[1]+1;
            diff[from] += num;
            diff[to] -= num;
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += diff[i];
            if (sum < nums[i]) {
                return false;
            }
        }
        return true;
    }
}
